package com.sort;

import java.util.Arrays;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/24 19:56
 * @description 异或运算
 * 相同为0  不同为1
 */
public class XorDemo {
    public static void main(String[] args) {
        //任何数和自己异或一定为0
        //N和0异或一定等于N
//        int[] arr = {1, 2};
//        swap(arr, 0, 1);
//        System.out.println(arr[0]);
//        System.out.println(arr[1]);
        XorDemo xorDemo = new XorDemo();
        xorDemo.find_two2(new int[]{1, 1, 2, 2, 3, 4});
    }

    public static void swap(int[] arr, int i, int j) {
        //数组的话必须保证这个i不等j 不然会洗成0
        //利用异或交换数组元素
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    //要求O(N)时间 和 O(1)空间
    //在一个数组中 只有一种数字出现奇数数字 找到他
    public void find_one(int[] arr) {
        int b = arr[0];
        for (int i = 1; i < arr.length; i++) {
            b ^= arr[i];
        }
        System.out.println(b);
    }

    //在一个数组中 只有两个数字出现了奇数次 找到他们
    public void find_two(int[] arr) {
        Arrays.sort(arr);
        int left = 0;
        int right = 1;
        while (right < arr.length) {
            if ((arr[left] ^ arr[right]) != 0) {
                System.out.println(arr[left]);
                System.out.println(arr[right]);
                break;
            } else {
                left += 2;
                right += 2;
            }
        }
    }

    public void find_two2(int[] arr) {
        int eor = 0;
        //假设两个奇数为a和b
        for (int i : arr) {
            eor ^= i;
        }
        //这里异或完之后 eor = a ^ b
        // eor !=0
        //eor 在某一个位置上一定是1
        //取出最右侧的1
        int right = eor & (~eor + 1);

        int eor2 = 0;
        for (int cur : arr) {
            if ((cur & right) == 1) {
                eor2 ^= cur;
            }
        }
        System.out.println(eor2 + "and " + (eor ^ eor2));
    }
}
